The Valiant–Vazirani theorem is a theorem in computational complexity theory. It was proven by Leslie Valiant and Vijay Vazirani in their paper titled "NP is as easy as detecting unique solutions" published in 1986.[1] The theorem states that if there is a polynomial time algorithm for Unambiguous-SAT, then NP=RP.
The theorem implies that even if the number of satisfying assignments is very small, SAT (which is an NP-complete problem) still remains a hard problem.
Unambiguous-SAT is the promise problem to decide whether a given Boolean formula is unsatisfiable or has exactly one satisfying assignment. In the first case a Unambiguous-SAT algorithm should reject, and in the second it should accept the formula. If the formula has more than one satisfying assignment then the behavior of the Unambiguous-SAT algorithm does not matter. Unambiguous-SAT belongs to complexity class UP.
The proof of Valiant–Vazirani theorem creates a probabilistic reduction from SAT to a limited number of instances of Unambiguous-SAT. By this reduction, if the original formula was unsatisfiable, none of Unambiguous-SAT problems are satisfiable. And if the original formula is satisfiable, then with probability ≥ 1/8, at least one of the Unambiguous-SAT instances has a unique satisfying assignment. Note that this probabilistic reduction introduces some error; however, the proof shows that the error is single-sided and completely avoids false-positives. The reduction relies also on universal hash functions to map the original SAT formula to multiple Unambiguous-SAT instances. By choosing different sizes of the hash set the authors create one instance of Unambiguous-SAT to have a solution with probability ≥1/8, if the original problem was satisfiable.